package _18_剑指OfferII;

import java.util.*;

public class _113_剑指OfferII课程顺序 {

    public static void main(String[] args) {

        _113_剑指OfferII课程顺序 v = new _113_剑指OfferII课程顺序();

        int[][] ins = {};

        System.out.println(Arrays.toString(v.findOrder(2, ins)));

    }

    // 拓扑排序，Khan算法
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 记录每个节点到达其他节点的集合
        List<Integer>[] list = new ArrayList[numCourses];
        int[] results = new int[numCourses];
        int index = 0;
        // 存储每个节点的入度集合
        int[] values = new int[numCourses];
        for (int[] prerequisite : prerequisites) {
            int to = prerequisite[0];
            int from = prerequisite[1];
            if (list[from] == null) {
                list[from] = new ArrayList<>();
            }
            list[from].add(to);
            // 每个节点的入度之和
            values[to]++;
        }

        // 拿出当前节点入度为0的集合
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; ++i) {
            if (values[i] == 0) {
                queue.add(i);
            }
        }
        while (!queue.isEmpty()) {
            int from = queue.poll();
            results[index++] = from;
            ArrayList<Integer> tos = (ArrayList<Integer>) list[from];
            if (tos == null) continue;
            for(int to: tos) {
                if (--values[to] == 0) {
                    queue.add(to);
                }
            }
        }

        return index == numCourses? results: new int[0];
    }
}
